package com.devshephard.rpcframework.acm.tree.util;

import org.springframework.security.core.parameters.P;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class DCSS {
    public static void main(String[] args) {

        char[][] board = {{'a','a','b','a','a','b'},{'a','a','b','b','b','a'},{'a','a','a','a','b','a'},{'b','a','b','b','a','b'},{'a','b','b','a','b','a'},{'b','a','a','a','a','b'}};
        String word = "bbbaabbbbbab";

       /* char[][] board = {{'L','L','A','B','L','D'},{'G','A','B','A','L','L'},{'A','B','C','B','J','A'},{'L','E','D','H','I','L'}};
        String word = "GABALJIHDCBA";*/

        char[] wordArr = word.toCharArray();

        DCSS dcss = new DCSS();
        boolean result = false;

            if(board.length * board[0].length < wordArr.length){
                result = false;
            }

            if(board.length == 1 && wordArr.length == 1 && board[0][0] == wordArr[0]){
                    result = true;
            }

            for (int j = 0; j < board.length; j++) {
                for (int k = 0; k < board[j].length; k++) {

                    if(wordArr[0] == board[j][k]){
                        if(wordArr.length == 1){
                            result = true;
                        }
                         int[][] checkInt = new int[10][10];
                         checkInt[j][k] = wordArr[0];
                         boolean search = dcss.search(word, 1, board, j - 1, k,checkInt);
                         boolean search1 = dcss.search(word, 1, board, j + 1, k,checkInt);
                         boolean search2 = dcss.search(word, 1, board, j, k - 1,checkInt);
                         boolean search3 = dcss.search(word, 1, board, j, k + 1,checkInt);
                         if(search == true || search1 == true || search2 == true || search3 == true){
                             result = true;
                             break;
                         }
                    }
                    else{
                        continue;
                    }
                }
            }
          System.out.println(result);
    }


    public static boolean search(String word,int point,char[][] chars,int x,int y,int[][] checkInt){

        if(x == -1 || x == chars.length || y == -1 || y == chars[x].length){
            return false;
        }

        char[] wordArr = word.toCharArray();

        if(point + 1 == wordArr.length){
            return true;
        }

        if(wordArr[point] == (chars[x][y])){

            if(!(x - 1 == -1) && wordArr[point + 1] == chars[x-1][y] )
            {
                checkInt[x][y] = wordArr[point];
                if( checkInt[x-1][y] == 0 ){
                    if(search(word,point + 1,chars,x-1,y,checkInt) == false){
                        checkInt[x - 1][y] = 0;
                    }else {
                        return true;
                    }
                }else {
                    checkInt[x][y] = 0;
                }
            }

            if(!(x + 1 == chars.length) && wordArr[point + 1] == chars[x+1][y] )
            {
                checkInt[x][y] = wordArr[point];
                if(checkInt[x+1][y] == 0 ){
                    if(search(word,point + 1,chars,x+1,y,checkInt) == false){
                        checkInt[x + 1][y] = 0;
                    }else {
                        return true;
                    }
                }else {
                    checkInt[x][y] = 0;
                }
            }

            if(!(y - 1 == -1) && wordArr[point + 1] == chars[x][y-1] )
            {

                checkInt[x][y] = wordArr[point];
                if(checkInt[x][y-1] == 0 ){

                    if(search(word,point + 1,chars,x,y-1,checkInt) == false){
                        checkInt[x][y - 1] = 0;
                    }else {
                        return true;
                    }
                }else {
                    checkInt[x][y] = 0;

                }
            }

            if(!(y + 1 == chars[x].length) && wordArr[point + 1] == chars[x][y+1] )
            {

                checkInt[x][y] = wordArr[point];
                if(checkInt[x][y+1] == 0 ){
                    if(search(word,point + 1,chars,x,y+1,checkInt) == false){
                        checkInt[x][y + 1] = 0;
                        return false;
                    }else {
                        return true;
                    }
                }else {
                    checkInt[x][y] = 0;
                }
            }
        }else {
            checkInt[x][y] = 0;
            return false;
        }
        checkInt[x][y] = 0;
        return false;
    }

}
